package leetcode.code0538;

import leetcode.helper.tree.TreeNode;

public class Solution extends Solution538 {
	public class Ans {
		public TreeNode node; // 头
		public int min; // 头下最小节点的累加和
	}

	@Override
	public TreeNode convertBST(TreeNode root) {
		if (root == null)
			return null;
		return this.convertBST(root, 0).node;
	}

	private Ans convertBST(TreeNode node, int val) {
		if (node == null)
			return null;
		TreeNode r = null;
		TreeNode l = null;
		int cur = node.val;
		Ans right = this.convertBST(node.right, val);
		if (right != null) {
			r = right.node;
			cur += right.min;
		} else {
			cur += val;
		}
		Ans ans = new Ans();
		ans.node = new TreeNode(cur);
		ans.min = ans.node.val;
		Ans left = this.convertBST(node.left, cur);
		if (left != null) {
			l = left.node;
			ans.min = left.min;
		}
		ans.node.right = r;
		ans.node.left = l;
		return ans;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
